import java.util.ArrayList;
import java.util.List;

public class Move //implements Comparable<Move>
{
	public static final byte DEPTH_LIMIT = 4;
	
	private Grid grid;
	private int depth;
	private int fromPosition;
	private int toPosition;
	private byte rollbackCell;
	
	private ArrayList<Move> followingMoves = new ArrayList<Move>();

	public Move(Grid grid, byte player)
	{
		this.fromPosition = -1;
		this.toPosition = -1;
		this.rollbackCell = -1;
		this.grid = grid;
		this.depth = 0;
		
		generateFollowingMoves(grid, player);
	}
	
	public Move(Grid grid, String move)
	{
		this.fromPosition = Grid.convert(move.substring(0, 2));
		this.toPosition = Grid.convert(move.substring(2, 4));
		this.rollbackCell = grid.getCell(toPosition);
		this.grid = new Grid(grid);
		this.depth = 0;
		
		execute();
	}
	
	public Move(Grid grid, byte player, String move, int depth)
	{
		this(grid, player, Grid.convert(move.substring(0, 2)), Grid.convert(move.substring(2, 4)), depth);
	}
	
	public Move(Grid grid, byte player, int fromPosition, int toPosition, int depth)
	{
		this.fromPosition = fromPosition;
		this.toPosition = toPosition;
		this.rollbackCell = grid.getCell(toPosition);
		this.grid = new Grid(grid);
		this.depth = depth;
		
		execute();
		generateFollowingMoves(this.grid, (byte) (player ^ 3));
	}
	
	private void generateFollowingMoves(Grid grid, byte player)
	{
		if(depth < DEPTH_LIMIT)
		{
			List<String> moves = Move.getValidMoves(grid, player);
			
			for(String move : moves)
			{
				followingMoves.add(new Move(grid, player, move, depth + 1));
			}
		}
	}
	
	public void execute()
	{
		grid.setCell(toPosition, grid.getCell(fromPosition));
		grid.setCell(fromPosition, (byte) 0);
	}
	
	public void rollback()
	{
		grid.setCell(fromPosition, grid.getCell(toPosition));
		grid.setCell(toPosition, rollbackCell);
	}
	
	public int getDepth()
	{
		return depth;
	}
	
	public Grid getGrid()
	{
		return grid;
	}
	
	public List<Move> getFollowingMoves()
	{
		return followingMoves;
	}
	
	public boolean isTerminalMove()
	{
		return followingMoves.size() == 0;
	}
	
	public boolean isWinningMove(byte player)
	{
		if(player == Grid.WHITE)
		{
			return toPosition > (Grid.CELL_COUNT - Grid.SIZE) << 1;
		}
		else if(player == Grid.BLACK)
		{
			return toPosition <= (Grid.SIZE) << 1;
		}
		
		return false;
	}
	
	@Override
	public String toString()
	{
		return Grid.convert(fromPosition) + Grid.convert(toPosition);
	}
	
	public static String getBestMove(Grid grid, byte player)
	{
		ArrayList<Move> bestMove = new ArrayList<Move>();
		Move initialBoard = new Move(grid, player);
		int bestValue = Integer.MIN_VALUE;
		
		for(Move m : initialBoard.getFollowingMoves())
		{
			if(System.currentTimeMillis() - Breakthrough.START_TIME < Breakthrough.MAX_TIME)
			{
				int value = Move.MMAB(m, player, Integer.MIN_VALUE, Integer.MAX_VALUE);
				
				if(value > bestValue)
				{
					bestValue = value;
					bestMove.clear();
				}
				
				if(value >= bestValue)
				{
					bestMove.add(m);
				}
			}
		}
		
		return bestMove.get((int) (Math.random() * bestMove.size())).toString();
	}
	
	public static int MMAB(Move move, byte player, int alpha, int beta)
	{
		// Time is up! Pick the best move from what we got so far...
		if(System.currentTimeMillis() - Breakthrough.START_TIME >= Breakthrough.MAX_TIME) return Integer.MIN_VALUE;
		
		if(move.isTerminalMove() || move.isWinningMove(player))
		{
			return move.getGrid().evaluate(player) >> move.getDepth();
		}
		
		// Max
		if(player == move.getGrid().getCurrentPlayer())
		{
			for(Move m : move.getFollowingMoves())
			{
				alpha = Math.max(alpha, MMAB(m, (byte) (player ^ 3), alpha, beta));
				
				if(beta <= alpha)
				{
					break;
				}
			}
			
			return alpha;
		}
		// Min
		else
		{
			for(Move m : move.getFollowingMoves())
			{
				beta = Math.min(beta, MMAB(m, (byte) (player ^ 3), alpha, beta));
				
				if(beta <= alpha)
				{
					break;
				}
			}
			
			return beta;
		}
	}
	
	public static List<String> getValidMoves(Grid grid, byte player)
	{
		List<String> moves = new ArrayList<String>();

		for(String position : grid.getPlayerPositions(player))
		{
			int p = Grid.convert(position);
			int direction = 0;
			
			if(player == Grid.WHITE)
			{
				direction = 1;
			}
			else if(player == Grid.BLACK)
			{
				direction = -1;
			}
			
			if((p >> 1) % Grid.SIZE != 0 && grid.getCell(p + direction * ((Grid.SIZE - direction) << 1)) != player)
			{
				moves.add(position.concat(Grid.convert(p + direction * ((Grid.SIZE - direction) << 1))));
			}
			
			if(grid.getCell(p + direction * (Grid.SIZE << 1)) == Grid.EMPTY)
			{
				moves.add(position.concat(Grid.convert(p + direction * (Grid.SIZE << 1))));
			}
			
			if(((p >> 1) + 1) % Grid.SIZE != 0 && grid.getCell(p + direction * ((Grid.SIZE + direction) << 1)) != player)
			{
				moves.add(position.concat(Grid.convert(p + direction * ((Grid.SIZE + direction) << 1))));
			}
		}
				
		return moves;
	}
}
